package com.lin.sort;

import org.junit.Test;

import java.util.Arrays;

public class Sort {


    /**
     * 交换数组中的两个数
     * @param arr 数组
     * @param a 下标a
     * @param b 下标b
     */
    public void swap(int[] arr, int a, int b){
        int t = arr[a];
        arr[a] = arr[b];
        arr[b] = t;
    }

    /**
     * node i
     * parent node i/2
     * left child node 2*i+1
     * right child node 2*i+2
     * @param arr 数组
     * @param i 节点
     */
    public void maxHeapify(int[] arr, int i, int len){
        while ((2*i+1) < len){
            int k = 2*i+1;
            if ( (k+1) < len && arr[k] < arr[k+1]){// 如果左节点小于右节点
                k++;// 指向右节点
            }
            if (arr[k] < arr[i]){
                break;
            }
            swap(arr, k, i);
            i = k;
        }
    }

    public void heapSort(int[] arr){
        // 构建最大堆
        for (int i = arr.length/2-1 ;i >= 0; i--) {
            maxHeapify(arr, i, arr.length);
        }

        for (int i = arr.length-1; i >= 0; i--) {
            swap(arr, i, 0);// 构建好最大堆后，将数组首尾交换
            maxHeapify(arr, 0, i);
        }
    }


    /**
     * 分而治之中的分
     * @param arr 数组
     * @param left 数组的第一个数
     * @param right 数组的第二个数
     */
    public void divide(int[] arr, int left, int right){
        if (left > right){
            return;
        }
        int mid = (left+right)/2;
        divide(arr, left, mid);
        divide(arr, mid+1, right);

    }

    /**
     * 合并(类似合并两个有序数组)
     *
     * @param arr 数组
     * @param left 数组的第一个数
     * @param right 数组的第二个数
     */
    public void merge(int[] arr, int left, int right, int mid){
        if (left == right){
            return;
        }
        int index = 0;
        int l = left;
        int r = mid+1;
        int[] arrtmp = new int[arr.length];
        while (l <= mid && r <= right){
            if (arr[l] >= arr[r]){
                arrtmp[index++] = l++;
            } else {
                break;
            }
        }
    }

    @Test
    public void testSort(){
        int[] arr = {8, 12, 3, 10, 5, 1, 45, 5};
        heapSort(arr);
//        swap(arr,1,2);
        System.out.println(Arrays.toString(arr));
    }

    public static void main(String[] args) {
        int[] arr = {8, 12, 3, 10, 5, 1, 45, 5};

        System.out.println(Arrays.toString(arr));
    }

}
